package com.nanbei.tree;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

/**
 * @ClassDescription:  树的基本操作
 * @JdkVersion: 17
 * @Author: BaoShan.li
 * @Created: 2023/12/6 14:27
 */
public class TreeTest {

    /**
     *          1
     *        /   \
     *       2      3
     *      / \    / \
     *     4   5  6   7
     *                 \
     *                  8
     *     前： 1、2、4、5、3、6、7
     *     中： 4、2、5、1、6、3、7
     *     后： 4、5、2、6、7、3、1
     */

    @Test
    public void test1() {
        TreeNode treeNode = new TreeNode(
                new TreeNode(new TreeNode(4), 2, new TreeNode(5)),
                1,
                new TreeNode(new TreeNode(6), 3, new TreeNode(null, 7, new TreeNode(8))));

//        System.out.println(maxDepth01(treeNode));
//        System.out.println(maxDepth03(treeNode));

        invertTree(treeNode);
    }

    /**
     * 遍历二叉树
     */
    @Test
    public void bianliTree() {

        TreeNode treeNode = new TreeNode(
                new TreeNode(new TreeNode(4), 2, new TreeNode(5)),
                1,
                new TreeNode(new TreeNode(6), 3, new TreeNode(7)));


        //定义一个栈用来记录节点
        LinkedList<TreeNode> treeNodes = new LinkedList<>();

        TreeNode curr = treeNode;
        TreeNode pop = null;
        while (curr != null || !treeNodes.isEmpty()) {
            if (curr != null) {
                treeNodes.push(curr);
                // 前序打印
                System.out.println((curr.value));
                // 处理左子树
                curr = curr.left;
            } else {
                TreeNode peek = treeNodes.peek();
                if (peek.right == null) {
                    // 没有右子树
                    pop = treeNodes.pop();
                    // 在此输出为后续遍历
                    System.out.println(pop.value);
                    // 在此输出为中序遍历
                    System.out.println(peek.value);
                } else if (peek.right == pop) {
                    // 右子树处理完成
                    pop = treeNodes.pop();
                    // 在此输出为后续遍历
                    System.out.println(pop.value);
                } else {
                    // 右子树待处理
                    // 在此输出为中序遍历
                    System.out.println(peek.value);
                    curr = peek.right;
                }
            }


        }

    }

    /**
     * 判断二叉树是否是对称二叉树
     */
    @Test
    public void isDuiChen() {
        TreeNode treeNode = new TreeNode(
                new TreeNode(new TreeNode(3), 2, new TreeNode(4)),
                1,
                new TreeNode(new TreeNode(4), 2, new TreeNode(3)));
        boolean check = check(treeNode.left, treeNode.right);
        System.out.println(check);

    }

    private boolean check(TreeNode left, TreeNode right) {
        // 如果两个都为空则返回 true
        if (left == null && right == null) {
            return true;
        }

        // 如果两个有一个为空，另外一个不为空 则返回false
        if (left == null || right == null) {
            return false;
        }

        // 如果两个值不同则返回 false
        if (left.value != right.value) {
            return false;
        }

        // 递归比较左子树的左孩子和右子树的右孩子 ，左子树的右孩子和右子树的左孩子
        return check(left.left, right.right) && check(left.right, right.left);


    }


    /**
     * 计算树的最大深度 （递归方法）
     *
     * @param treeNode 树
     * @return 树的最大深度
     */
    public static int maxDepth01(TreeNode treeNode) {
        if (treeNode == null) {
            return 0;
        }

        // 当前节点为叶子节点时
        if (treeNode.right == null && treeNode.left == null) {
            return 1;
        }

        // 当前节点为非叶子节点
        int leftDepth = maxDepth01(treeNode.left);
        int rightDepth = maxDepth01(treeNode.right);
        return Integer.max(leftDepth, rightDepth) + 1;
    }


    /**
     * 计算树的最大深度 （后续遍历方法）
     *
     * @param treeNode 树
     * @return 树的最大深度
     */
    public static int maxDepth02(TreeNode treeNode) {

        LinkedList<TreeNode> treeNodes = new LinkedList<>();
        TreeNode pop = null;
        TreeNode curr = treeNode;
        int size = 0;
        while (curr != null || !treeNodes.isEmpty()) {
            if (curr != null) {
                treeNodes.push(curr);
                // 在后续遍历中 栈最大的长度就是树的最大深度
                size = Math.max(size, treeNodes.size());
                curr = curr.left;
            } else {
                TreeNode peek = treeNodes.peek();
                if (peek.right == null || peek.right == pop) {
                    pop = treeNodes.pop();
                } else {
                    curr = peek.right;
                }
            }
        }

        return size;
    }

    /**
     * 计算树的最大深度 （层次遍历）
     *
     * @param treeNode 树
     * @return 树的最大深度
     */
    public static int maxDepth03(TreeNode treeNode) {

        if (treeNode == null) {
            return 0;
        }

        // 原来存放节点的队列
        LinkedList<TreeNode> treeNodes = new LinkedList<>();

        treeNodes.offer(treeNode);
        int depth = 0;
        while (!treeNodes.isEmpty()) {
            // 获取当前层级有多少个元素，然后进行对当前层级元素进行遍历
            int size = treeNodes.size();
            for (int i = 0; i < size; i++) {
                TreeNode poll = treeNodes.remove();
                // 将左孩子和右孩子放入队列
                if (poll.left != null) {
                    treeNodes.offer(poll.left);
                }

                if (poll.right != null) {
                    treeNodes.offer(poll.right);
                }
            }
            depth++;
        }

        return depth;

    }


    /**
     * 计算树的最小深度 （递归遍历）
     * 5
     * /
     * 6
     *
     * @param treeNode 树
     * @return 树的最大深度
     */
    public static int minDepth01(TreeNode treeNode) {
        if (treeNode == null) {
            return 0;
        }

        int leftDepth = minDepth01(treeNode.left);
        int rightDepth = minDepth01(treeNode.right);

        if (leftDepth == 0) {
            // 如果根节点没有左子树  则返回右子树的最小深度
            return rightDepth;
        }
        if (rightDepth == 0) {
            // 如果根节点没有右子树  则返回左子树的最小深度
            return leftDepth;
        }

        return Integer.min(rightDepth, leftDepth) + 1;
    }


    /**
     * 计算树的最大深度 （层次遍历）
     *
     * @param treeNode 树
     * @return 树的最大深度
     */
    public static int minDepth03(TreeNode treeNode) {

        if (treeNode == null) {
            return 0;
        }

        // 原来存放节点的队列
        LinkedList<TreeNode> treeNodes = new LinkedList<>();
        treeNodes.offer(treeNode);
        int depth = 0;
        while (!treeNodes.isEmpty()) {
            depth++;
            // 获取当前层级有多少个元素，然后进行对当前层级元素进行遍历
            int size = treeNodes.size();
            for (int i = 0; i < size; i++) {
                TreeNode poll = treeNodes.remove();

                if (poll.left == null && poll.right == null) {
                    return depth;
                }
                // 将左孩子和右孩子放入队列
                if (poll.left != null) {
                    treeNodes.offer(poll.left);
                }

                if (poll.right != null) {
                    treeNodes.offer(poll.right);
                }
            }
        }
        return depth;

    }


    /**
     * 反转二叉树
     *
     * @param treeNode 树
     */
    public void invertTree(TreeNode treeNode) {
        if (treeNode == null) {
            return;
        }

        // 交换左右孩子节点
        TreeNode tmp = treeNode.right;
        treeNode.right = treeNode.left;
        treeNode.left = tmp;

        // 递归交换左子树
        invertTree(treeNode.left);
        // 递归交换右子树
        invertTree(treeNode.right);

    }


    /**
     *  根据后缀表达式建树
     *      *
     *     /  \
     *    -    3
     *   / \
     *  2   1
     * 中缀表达式 （2-1）*3
     * 后缀表达式（逆波兰表达式）  21-3*
     * <p>
     * 遇到数字入栈
     * 遇到运算符出栈
     * 先出栈的为右孩子  后出栈的为左孩子
     */
    @Test
    public void buildTree() {
        TreeNodeStr treeNodeStr = buildTree(new String[]{"2", "1", "-", "3", "*"});
    }


    public TreeNodeStr buildTree(String[] nodes) {

        // 先定义一个栈
        LinkedList<TreeNodeStr> treeNodeStrList = new LinkedList<>();

        // 遍历数组
     /*   for (String node : nodes) {
            switch (node) {
                case "+", "-", "*", "/" -> {
                    TreeNodeStr right = treeNodeStrList.pop();
                    TreeNodeStr left = treeNodeStrList.pop();
                    TreeNodeStr parentNode = new TreeNodeStr(node);
                    parentNode.right = right;
                    parentNode.left = left;
                    treeNodeStrList.push(parentNode);
                }
                default -> {
                    treeNodeStrList.push(new TreeNodeStr(node));
                }
            }
        }*/
        return treeNodeStrList.pop();
    }


    /**
     *  根据前序和中序构建树
     *        1
     *      /   \
     *     2     3
     *    /     / \
     *   4     6   7
     *  preOrder 前序遍历[1,2,4,3,6,7]
     *  inOrder 中序遍历[4,2,1,6,3,7]
     *
     *  根 1
     *                     per      in
     *  左子树遍历的节点     2,4     4,2
     *  右子树遍历的节点     3,6,7   6,3,7
     *
     *
     *                     per      in
     *  根 2
     *  左子树遍历的节点     4        2
     *  根 3
     *  右子树遍历的节点     6         6
     *  右子树遍历的节点     7         7
     *
     **/
    @Test
    public void buildTreeByOrder() {
        TreeNode treeNode = buildTreeByOrder(new int[]{1, 2, 4, 3, 6, 7}, new int[]{4, 2, 1, 6, 3, 7});
    }

    /**
     * @param preOrder 前序遍历[1,2,4,3,6,7]
     * @param inOrder  中序遍历[4,2,1,6,3,7]
     **/
    public TreeNode buildTreeByOrder(int[] preOrder, int[] inOrder) {

        if (preOrder.length ==0 || inOrder.length==0){
            return null;
        }

        int rootValue = preOrder[0];
        // 定义根节点
        TreeNode rootNode = new TreeNode(rootValue);

        for (int i = 0; i < inOrder.length; i++) {
            if (inOrder[i] == rootValue) {
                // 前序遍历的左子树节点
                int[] preLeft = Arrays.copyOfRange(preOrder, 1, i + 1); // [2,4]
                // 前序遍历的右子树节点
                int[] preRight = Arrays.copyOfRange(preOrder, i + 1, preOrder.length); //[3,6,7]

                // 中序遍历的左子树节点
                int[] inLeft = Arrays.copyOfRange(inOrder, 0, i); //[4,2]
                // 中序遍历的右子树节点
                int[] inRight = Arrays.copyOfRange(inOrder, i + 1, inOrder.length); //[6,3,7]

                // 递归调用后返回的根节点的左孩子
                rootNode.left = buildTreeByOrder(preLeft, inLeft);
                // 递归调用后返回的根节点的右孩子
                rootNode.right = buildTreeByOrder(preRight, inRight);

                break;
            }
        }

        return rootNode;
    }


    /**
     /**
     *  根据前序和中序构建树
     *        1
     *      /   \
     *     2     3
     *    /     / \
     *   4     6   7
     *  inOrder   中序遍历[4,2,1,6,3,7]
     *  postOrder 后续遍历[4,2,6,7,3,1]
     *
     * @param inOrder   中序遍历[4,2,1,6,3,7]
     * @param postOrder 后续遍历[4,2,6,7,3,1]
     * @return 创建好的树
     */
    public TreeNode buildTreeByPostOrder(int[] inOrder, int[] postOrder) {
        if (inOrder.length == 0 || postOrder.length == 0) {
            return null;
        }

        int rootValue = postOrder[postOrder.length - 1];
        // 定义根节点
        TreeNode rootNode = new TreeNode(rootValue);

        for (int i = 0; i < inOrder.length; i++) {
            if (inOrder[i] == rootValue) {
                // 后序遍历的左子树节点
                int[] postLeft = Arrays.copyOfRange(postOrder, 0, i); // [4,2]
                // 后序遍历的右子树节点
                int[] postRight = Arrays.copyOfRange(postOrder, i, postOrder.length - 1); //[3,6,7]

                // 中序遍历的左子树节点
                int[] inLeft = Arrays.copyOfRange(inOrder, 0, i); //[4,2]
                // 中序遍历的右子树节点
                int[] inRight = Arrays.copyOfRange(inOrder, i + 1, inOrder.length); //[6,7,3]

                // 递归调用后返回的根节点的左孩子
                rootNode.left = buildTreeByPostOrder(inLeft, postLeft);
                // 递归调用后返回的根节点的右孩子
                rootNode.right = buildTreeByPostOrder(inRight, postRight);

                break;
            }
        }

        return rootNode;
    }


    /**
     * 删除二叉搜索树的节点
     *
     * @param root 二叉搜索树
     * @param key  要删除的key
     * @return 删除后的树
     */
    public static TreeNode deleteNode(TreeNode root, int key) {
        TreeNode node = root;
        TreeNode parent = null;
        while (node != null) {
            if (key > node.value) {
                parent = node;
                node = node.right;
            } else if (key < node.value) {
                parent = node;
                node = node.left;
            } else {
                break;
            }
        }
        if (node == null) {
            return root;
        }

        if (node.left == null) {
            if (parent == null) {
                root = node.right;
            } else if (parent.right == node) {
                parent.right = node.right;
            } else {
                parent.left = node.right;
            }
        } else if (node.right == null) {
            if (parent == null) {
                root = node.left;
            } else if (parent.right == node) {
                parent.right = node.left;
            } else {
                parent.left = node.left;
            }
        } else {
            //既有左孩子又有右孩子
            TreeNode parentSuccessor = node;
            TreeNode success = node.right;
            while (success.left != null) {
                parentSuccessor = success;
                success = success.left;
            }
            if (parentSuccessor != node) {
                parentSuccessor.left = success.right;
                success.right = node.right;
            }
            if (parent == null) {
                root = success;
            } else if (parent.right == node) {
                parent.right = success;
            } else {
                parent.left = success;
            }
            success.left = node.left;
        }
        return root;
    }

    /**
     * 使用递归向二叉搜索树中添加节点
     *
     * @param node 树
     * @param val  要添加的值
     * @return 添加后返回的树
     */
    public TreeNode insertIntoBST(TreeNode node, int val) {
        if (node == null){
            return new TreeNode(val);
        }

        if (node.value > val){
            node.left = insertIntoBST(node.left,val);
        }else {
            node.right = insertIntoBST(node.right,val);
        }
        return node;
    }


    /**
     * 中序遍历
     * 验证二叉搜索树
     * @param root 树节点
     * @return 是否是二叉搜索树
     */
    public boolean isValidBST(TreeNode root) {
        TreeNode node = root;
        long num = Long.MIN_VALUE;
        LinkedList<TreeNode> nodeLinkedList = new LinkedList<>();
        while (node != null || !nodeLinkedList.isEmpty()){
            if (node != null) {
                nodeLinkedList.push(node);
                node = node.left;
            }else {
                TreeNode pop = nodeLinkedList.pop();
                if (pop.value > num) {
                    num = pop.value;
                }else {
                    return false;
                }
                node = pop.right;
            }

        }
        return true;
    }


    @Test
    public void testBstFromPreorder(){
        TreeNode treeNode = bstFromPreorder2(new int[]{8, 5, 1, 7, 10, 12});
    }

    /**
     * 递归遍历
     * 根据前序遍历的数组构建二叉排序树
     * @param preorder 前序遍历的数组
     * @return 构建完成的排序二叉树
     */
    public TreeNode bstFromPreorder(int[] preorder) {
        TreeNode treeNode = new TreeNode(preorder[0]);

        for (int i = 1; i < preorder.length; i++) {
            treeNode = buildBST(treeNode, preorder[i]);
        }
        return treeNode;
    }

    private TreeNode buildBST(TreeNode treeNode, int val) {
        if (treeNode == null){
            return new TreeNode(val);
        }
        if (val > treeNode.value){
            treeNode.right = buildBST(treeNode.right,val);
        }
        if (val < treeNode.value){
            treeNode.left = buildBST(treeNode.left,val);
        }
        return  treeNode;
    }


    /**
     * 使用分治法
     * 根据前序遍历的数组构建二叉排序树
     * @param preorder 前序遍历的数组
     * @return 构建完成的排序二叉树
     */
    public TreeNode bstFromPreorder2(int[] preorder) {
        return buildBST(preorder, 0, preorder.length - 1);
    }
    private TreeNode buildBST(int[] preorder, int start,int end) {
        if (start > end){
            return null;
        }
        TreeNode treeNode = new TreeNode(preorder[start]);
        int index = start+1;
        while (index < end){
            index++;
            if (preorder[index] > preorder[0]){
                break;
            }
        }
        treeNode.left = buildBST(preorder,start+1,index-1);
        treeNode.right = buildBST(preorder,index,end);
        return treeNode;

    }


    /**
     * 给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
     * @param root 二叉搜索树
     * @param p 节点
     * @param q 节点
     * @return 公共祖先
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        TreeNode node = root;
        while (node != null) {
            if (node.value > p.value && node.value > q.value){
                node = node.left;
            }else if (node.value < p.value && node.value < q.value){
                node = node.right;
            }else {
                break;
            }
        }
        return node;
    }

}